• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention relates to a tracking server that receives GPS data from a location tracking device located in a vehicle. GPS data describes a route that is representative of a vehicle route used to complete a journey from an initial location to a destination location. The tracking server identifies noisy GPS data included in the received GPS data and reviews a part of the route by responding to the noisy GPS data. The tracking server updates a map database to include one or more road segments associated with the revised part of the route. In addition, the tracking server can calculate a fare for the trip based on the revised route.
    公开号:BR112018015201B1
    申请号:R112018015201-3
    申请日:2016-12-31
    公开日:2021-02-23
    发明作者:Sophia Cui；Thi Duong Nguyen；Theodore Russell Sumers；Miao Yu；Xingwen Zhang
    申请人:Uber Technologies, Inc；
    IPC主号:
    专利说明:

    TECHNICAL FIELD
    [001] The embodiments described in this document generally relate to associating global positioning system (GPS) data with road segments to update maps using GPS data and to calculate travel distances based on GPS data. BACKGROUND
    [002] Current GPS systems use GPS data from a location tracking device located in a vehicle to perform various functions such as travel distance and fare calculations. However, GPS data typically includes noise, which results in inaccurate GPS data that is not representative of the actual location of the location tracking device. Calculating travel distances based on inaccurate GPS data can result in incorrect fare calculation. SUMMARY
    [003] A vehicle operator provides services such as transporting a person or goods to a requested destination. A tracking server is in communication with a location tracking device that is located inside the vehicle and receives GPS data from the location tracking device as the vehicle moves (for example, it moves) to complete a transport service (for example, also referred to in this document as a journey) from an initial location to the requested destination.
    [004] In some cases, some of the GPS data received from the location tracking device may include erroneous data due to an inaccurate GPS signal received by the location tracking device (for example, as a result of noise, signal, etc.). Thus, the received GPS data may not accurately reflect the true position of the location tracking device, and may cause processing errors after the trip is completed. In order to mitigate potential errors in the data associated with a trip, the tracking server can review a part of a trip's route based on the received GPS data. The part of the route that is reviewed by the tracking server corresponds to the noisy GPS data. By reviewing the route that is representative of the trip, the tracking server ensures that the route reviewed accurately reflects the actual route of the transport vehicle during the trip.
    [005] The revised portion of the journey's route path may include one or more road segments used by the vehicle to complete the journey that are not included in a database of known road segment maps. The tracking server can review the map database to include one or more segments in this way, improving the coverage of the specified highway segments in the map database. Additionally, due to the revised route accurately reflecting the actual route of the transport vehicle used to complete the journey, the tracking server can also calculate a more accurate fare for the journey that the person pays in exchange for the service.
    [006] The aspects and advantages described in this summary and the following detailed description do not cover everything. Various aspects and additional advantages will be apparent to those skilled in the art in view of the drawings, the specification and the claims. BRIEF DESCRIPTION OF THE DRAWINGS
    [007] FIGURE 1 illustrates a system architecture of a mapping system according to an embodiment.
    [008] FIGURE 2 illustrates a detailed view of a path determination module included in the mapping system shown in Figure 1 according to an embodiment.
    [009] FIGURE 3 illustrates GPS data associated with a trip according to an embodiment.
    [0010] FIGURE 4 illustrates a route path associated with a map and a simplified GPS route according to an embodiment.
    [0011] FIGURE 5 illustrates a final route according to an embodiment.
    [0012] FIGURE 6 illustrates an updated map based on the simplified GPS route according to an embodiment.
    [0013] FIGURE 7A is a flow of the method for calculating a rate for a trip, according to one embodiment.
    [0014] FIGURE 7B is a flow of the method for updating a map, according to an embodiment.
    [0015] FIGURE 8 illustrates a computer system that implements the embodiments in this document according to one embodiment.
    [0016] FIGURE 9 illustrates a mobile computing device that implements the embodiments in this document according to one embodiment.
    [0017] The figures represent various embodiments for the purpose of illustration only. Those skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated in this document can be employed without departing from the principles described in this document. DETAILED DESCRIPTION System Overview
    [0018] FIGURE 1 illustrates a system architecture of a tracking server 100 according to an embodiment. In particular, FIGURE 1 illustrates a detailed view of modules within a tracking server 100, a tracking device 101 and a service requesting device 103 according to one embodiment. Some embodiments of the tracking server 100, the tracking device 101 and the service requesting device 103 have different modules than those described in this document. Similarly, functions can be distributed among modules in a different way than described in this document. As used in this document, the term "module" refers to the computer program logic used to provide the specified functionality. Thus, a module can be implemented in hardware, firmware and / or software.
    [0019] In one embodiment, the tracking server 100 implements a network service, such as a provisioning service, which allows services to be arranged between parties as well as between users of the location tracking device 101 and of the service requesting device 103. As described in this document, a location tracking device 101 may correspond to a mobile computing device, such as a smartphone, that is operated by a service provider, such as a vehicle driver, or it may correspond to a vehicle's built-in computer system. The tracking server 100 can also correspond to a set of servers, in some examples, and can operate with or as part of another system that implements network services. An example of services includes arranging a transport service or a delivery service between a service requester and a service provider. In the context of the discussion in this document, a transport vehicle operator (for example, the service provider) provides the service of transporting a person (for example, the requester) to a destination requested by the person. In one embodiment, transport vehicles include personal vehicles such as cars and motorcycles as well as public transport vehicles such as trains, trams, buses, etc.
    [0020] In one embodiment, transporting a person from an initial location to a destination location is referred to as a journey. Generally, tracking server 100 calculates fares for trips. A tariff is a monetary payment from a service requester to a service provider in exchange for the service provider transporting the service requester to a destination location. In one embodiment, tracking server 100 also updates maps based on the route paths taken by transport vehicles to complete trips.
    [0021] Tracking server 100 receives raw GPS data from a location tracking device 101 included in a transport vehicle as the transport vehicle moves its position. Raw GPS data can include noise, in the form of erroneous data. Since the raw GPS data includes noise, the GPS data may not accurately reflect the true position of the location tracking device 101 at the time the GPS data was measured. The noise in the GPS data can result from an absence of an accurate GPS signal received by the location tracking device due to constructions blocking the GPS signal, for example. Tracking server 100 can compare raw GPS data with a trip associated with a map. In one embodiment, a trip associated with a map is representative of a probable route path as determined by tracking server 100 according to the raw GPS data as will be further described below. Tracking server 100 determines whether the raw GPS data corresponds to the trip associated with the map based on the comparison.
    [0022] In one embodiment, the tracking server 100 can review a portion of the trip that corresponds to the noisy GPS data to accurately reflect the actual path of the transport vehicle during the trip. Some parts of the trip may still not correspond to the trip associated with the map due to the transport vehicle not using known road networks. Tracking server 100 determines whether to use the revised portion of the trip corresponding to the noisy GPS data or the trip associated with the map when calculating the fare for the trip. Tracking server 100 can also update road networks based on GPS data from location tracking device 101.
    [0023] As shown in FIGURE 1, the tracking server 100 is in communication with the location tracking device 101 and the service requesting device 103 via a network 105. In one embodiment, network 105 is the Internet or any combination of a LAN, a MAN, a WAN, a mobile, wired or wireless network, a private network, or a virtual private network. Although only a single location tracking device 101 and a single service requesting device 103 are shown in FIGURE 1, several location tracking devices 101 can be in communication with the tracking server 100.
    [0024] In one embodiment, the service requesting device 103 is an electronic device (for example, a smartphone) from a person who has requested a trip. Service requesting device 103 is used by the person to request a trip from a home location to a destination location via a service application 109 included with service requesting device 103. Service application 109 allows the user of the requesting device to service 103 submits a travel request, which the tracking server 100 then processes in order to select an operator of a transport vehicle.
    [0025] According to examples, the travel request may include (i) a user identifier (ID), (ii) a collection location (for example, a location identifier of the current position of the service requesting device 103 as determined by a GPS 107A module included in service requesting device 103, (iii) a destination location, and / or (iv) a vehicle type. For example, the GPS 107A module uses sensors (for example, a GPS receiver ) included in the service requesting device 103 to determine the position of the service requesting device 103 at various points in time. In one embodiment, the current position of the service requesting device 103 is represented by a location identifier such as latitude coordinates and The current position of the service requesting device 103 can also be associated with a time stamp indicating the time and / or date on which the GPS module 107A measured the current position of the device. service requesting device 103. Alternatively, the collection location of the service requesting device 103 can be manually entered on the service requesting device 103 by the user of device 103, such as by selecting a location on a map or in the form of an address including at least the number and name of a street.
    [0026] The disposition service, which is implemented by the tracking server 100 and / or by other servers or systems, can receive the travel request through network 105 and can select an operator or service provider for the requester. In an example, the disposition service may (i) identify a set of service providers that are available to provide the requested service and satisfy one or more conditions (for example, they have the specified vehicle type, and / or are within a predetermined distance or estimated travel time away from the collection location), (ii) select a service provider from the set of service providers, and (iii) transmit an invitation to the location tracking device 101 from your service provider. The invitation can include the collection location, so that the selected service provider can navigate to the collection location to start the journey for the requester. If the selected service provider accepts the invitation for providing input to the location tracking device 101, the tracking server 100 may consequently notify the service requesting device 103.
    [0027] In one embodiment, the location tracking device 101 is an electronic device (for example, a smartphone) located inside the transport vehicle used to complete trips. The location tracking device 101 includes a service application 111. The service application 111 displays, on the location tracking device 101, information about a trip that the service provider has agreed to provide, such as the collection location, and / or navigation and / or mapping information instructing the service provider to navigate to the collection location. As noted in this document, the collection location can be the current location of the service requesting device 103 or a user-specified location of the service requesting device 103. The service application 111 can also display, on the location tracking device 101, the destination of the requested trip if provided by the user of the service requesting application 111.
    [0028] The location tracking device 101 includes a GPS module 107B. The GPS module 107B uses one or more sensors from the location tracking device 101 to identify GPS data from the transport vehicle as the transport vehicle moves along one or more highways to complete a journey. The GPS data of the transport vehicle is representative of the position of the transport vehicle in different places in time during a journey. For example, at time t = T1, the location tracking device 101 can be at a particular GPS location, identified by a location identifier (for example, latitude and longitude coordinates) and a time stamp indicating the time and / or the date when the location tracking device 101 measured your current position. If the transport vehicle is moving, at time T = T2, the location tracking device 101 may be in a different GPS location. In this way, the location tracking device 101 periodically measures the current position of the transport vehicle (for example, every three seconds, every four seconds, etc.) and provides GPS data that is representative of the position of the transport vehicle over time for the tracking server 100. Alternatively, the location tracking device 101 can provide GPS data whenever new or updated measurements of the current position of the transport vehicle are made or are available.
    [0029] Each of the service applications 111 and 109 respectively stored on the location tracking device 101 and the service requesting device 103 may include or use an application programming interface (API) to communicate data to the tracking server. 100. The API can provide access to the tracking server 100 via secure access channels over the network 105 through various methods, such as forms based on the Network, programmatic access via restful APIs ("with representational state transfer capability" ), Simple Object Access Protocol (SOAP), remote procedure calls (RPC), script access, etc., while also providing secure access methods including key-based access to ensure that the tracking system 100 remains secure and only authorized users, service providers, and / or third parties can gain access to the tracking server 100.
    [0030] As shown in FIGURE 1, the tracking server 100 comprises a map database 113. The map database 113 stores several spatial map databases. Spatial map databases are databases that can be consulted by identifying different points (for example, having a latitude and longitude, and / or an altitude) along the travel paths that a given transport vehicle can use, and information about how different points connect with other points. Some commercially available spatial databases of maps include points identifying locations of interests and landmarks.
    [0031] With respect to vehicles, a database of vehicle maps can include points corresponding to locations on tracks, highways, expressways, etc. The vehicle's map database can also include other information related to lanes, such as intersections, one-way streets, how different highways and streets connect with each other, etc. Similarly, with respect to aircraft, a spatial database of the aircraft's map system can include points corresponding to locations along the air path and which points are limits for no flight zone, while for trains, a database The spatial map of a train's map system may include points corresponding to locations on the railroad and railroads, and where / how the railways connect. Additional map databases can be created or modified in the map database 113 as a result of real-life updates and modifications.
    [0032] Device interface 117 manages communication between tracking server 100, location tracking device 101 and service requesting device 103 over network 105. Device interface 117 receives travel requests from the requesting device Service 103 and transmit invitations to location tracking device 101. In addition, device interface 117 receives travel acceptances from location tracking device 101 and directs notifications of travel acceptances to service requesting device 103 In one embodiment, device interface 117 receives GPS data and / or status information about the service provider or service application 111 from the location tracking device 101 as the transport vehicle moves to complete a trip and sends the GPS data to a route determination module 119 included in the server tracking r 100.
    [0033] FIGURE 2 illustrates a block diagram illustrating the modules of the path determination module 119 according to an embodiment. Generally, the different modules included in the route determination module 119 collectively allow the route determination module 119 to determine the journey path along one or more routes that a transport vehicle is using to complete a journey. The route determination module 119 determines the travel path of the transport vehicle using GPS data received from a location tracking device 101 included in the transport vehicle.
    [0034] As shown in FIGURE 2, the route determination module 119 includes a map association module 201. The map association module 201 determines a route of one or more roads (for example, streets, expressways , and / or highways) that the transport vehicle uses to complete a journey. In another embodiment, the map association module 201 calculates the route at the conclusion of the trip or at intermediate moments during the trip, at the performer's will. In one embodiment, the route of travel of the transport vehicle used to complete a journey is considered the route of travel associated with the map of the transport vehicle. As the map association module 201 receives GPS data at different locations in time from the location tracking device 101 included in the transport vehicle, the map association module 201 attempts to identify which lanes the transport vehicle is on. is going through.
    [0035] In one embodiment, the map association module 201 queries the map database 113 for a vehicle map database. The map association module 201 uses the vehicle map database to identify one or more candidate points from the vehicle map database that correspond to a given GPS point included in the GPS data received from the GPS device. location tracking 101. A candidate point is a point having a latitude and longitude corresponding to a known location in the vehicle's map database. For example, in the vehicle map database, a candidate point can be a point that corresponds to a location on a street or at an intersection between several streets. As a result, the map association module 201 can identify a candidate point that best matches each GPS point included in the received GPS data.
    [0036] In one embodiment, the map association module 201 identifies one or more candidate points for a given GPS point because the GPS point may not be accurate due to noise in the GPS signal received from the location tracking device 101. The map association module 201 can determine that a GPS point is potentially inaccurate based on a comparison of the GPS point with a corresponding point (for example, latitude and longitude coordinates) on a route path associated with a map such as is described below. In one embodiment, the point from the route path associated with the map that corresponds to a GPS point is a point from the route path associated with the map that is closest to the GPS point in terms of distance. Since the GPS data may be inaccurate, the GPS data received from the location tracking device 101 may not necessarily correspond to the actual position of the location tracking device 101. In one embodiment, the location association module map 201 identifies one or more candidate points in the vehicle's map database that are within a predetermined distance from the GPS point.
    [0037] As the location tracking device 101 moves and provides updated GPS data at different locations in time for the map association module 201 or at the conclusion of the trip, the map association module 201 continues to identify candidate points for each GPS point in each instance in time. Alternatively, the map association module 201 can identify candidate points for a subset of the GPS points included in the GPS data. The map association module 201 determines the most likely route path (i.e., the route path associated with the map) based on the candidate points identified in the vehicle's map database.
    [0038] In one embodiment, the map association module 201 selects a map association model to determine the most likely route path based on the identified candidate points. For example, the map association module 201 can use a hidden Markov model solver, a targeting mechanism, a physical property mechanism, or other models, individually or in combination, to determine the vehicle's most likely route path. of transport including the location tracking device 101. In one embodiment, the determined route path of the transport vehicle used to complete a journey is considered to be the route path associated with the map. The determined route route is considered to be "associated with a map" as long as the route route links known road segments included in the vehicle's map database.
    [0039] The detection module 203 detects GPS points included in the GPS data that are candidates to be potentially inaccurate due to noise in the GPS signal. If a GPS point is determined to be inaccurate, the GPS point does not accurately reflect the actual position of the location tracking device 101 at the time when the GPS point was measured. In one embodiment, the detection module 203 detects GPS points that are candidates for being inaccurate based on the route path associated with the map determined by the map association module 201.
    [0040] To determine GPS points that are candidates to be inaccurate, the detection module 203 compares GPS points from the GPS data received with points of the route path associated with the map for a trip. Detection module 203 can declare a GPS point as a candidate to be inaccurate based on the accuracy of the GPS point compared to the route path associated with the map.
    [0041] In one embodiment, the accuracy of a GPS point is based on an error in estimating the position of the GPS point. The GPS point position estimation error describes the deviation in distance (for example, meters) between the GPS point and its corresponding point on the route path associated with the map for the trip. In one embodiment, a GPS point that is within a limit distance (for example, 5 meters) from its corresponding point on the route path associated with a map for a trip is considered accurate by detection module 203. Conversely, a GPS point that is located at a position greater than the limit distance from its corresponding point on the route path associated with the map for the trip is considered a candidate to be inaccurate. As a result of comparing GPS points with the route path associated with the map, detection module 203 can determine sequences of GPS points that are candidates for being inaccurate. Note that in the discussion in this document, the various threshold distances are established by an executor of the tracking server 100.
    [0042] FIGURE 3 illustrates raw GPS data from the location tracking device 101 that completed a trip according to one embodiment. FIGURE 3 illustrates only a portion of all GPS data included in a trip for ease of discussion. In FIGURE 3, according to the GPS data for a trip, a transport vehicle completed a trip starting at Street B at time t = 0 and ending at Street E at time t = 260. Each point shown in FIGURE 3 represents a GPS point included in the GPS data for a trip and the dashed line 301 that connects the GPS points in FIGURE 3 represents the GPS travel path of the transport vehicle. The GPS travel path represents the travel path of the transport vehicle according to the raw GPS data received from the location tracking device 101 including on the transport vehicle. FIGURE 3 also illustrates a route path associated with the map determined by the map association module 201 based on the received GPS data. The route path associated with the map is represented by a continuous line 303 in FIGURE 3.
    [0043] For each GPS point shown in FIGURE 3, detection module 203 compares the GPS point with a corresponding point from the route path associated with the map to determine the accuracy for each GPS point. For example, detection module 203 can determine that the GPS points between time t = 0 and time t = 100 and between time t = 150 and time t = 260 as accurate based on the comparison. However, the detection module 203 can determine that the GPS points of the GPS path between time t = 125 and time t = 145 are potentially inaccurate. As mentioned above, detection module 203 can determine that a GPS point from the GPS route path is potentially inaccurate based on a magnitude of the GPS point position estimation error with respect to the route path associated with the map. For example, detection module 203 determines for the GPS point at time t = 125 that the GPS point is potentially inaccurate due to its "d" position estimation error with respect to a corresponding point on the route path associated with map is greater than the limit distance. The limit distance represents a maximum deviation in the location between a position of a GPS point on the GPS route and a corresponding point on the route associated with the map before the GPS point is considered to be potentially inaccurate.
    [0044] Referring again to FIGURE 2, the route determination module 119 also includes a route creation module 205. The route creation module 205 simplifies parts of the GPS route path. In one embodiment, the route creation module 205 creates a simplified route path for those parts of the GPS route path that correspond to potentially inaccurate GPS point sequences. For example, the route creation module 205 can create a simplified route path for the GPS points between time t = 125 and time t = 145 shown in FIGURE 3. By simplifying parts of the GPS route path that are potentially inaccurate, the route creation module 205 reduces the impact of inaccurate points on the route path reported by the location tracking device 101.
    [0045] To simplify a part of the GPS route path, the 205 route creation module can apply an algorithm to reduce the number of points on a curve. In one embodiment, the route creation module 205 can apply the Ramer - Douglas - Peucker (RDP) algorithm conventionally known for GPS points classified as potentially inaccurate. The route creation module 205 recursively divides the line between the GPS points classified as potentially inaccurate. Initially, the route creation module 205 is provided with the points between the first and the last GPS point that require simplification such as the GPS points between time t = 125 and time t = 145 shown in FIGURE 3. The route creation module 205 automatically marks the first GPS point (for example, at time t = 125) and the last GPS point (for example, at time t = 145) to be saved. The route creation module 205 then identifies the point that is furthest from a straight line segment between the first and the last point. For example, the route creation module 205 identifies the GPS point at time t = 131 because it is farthest from a straight line segment between the first GPS point at t = 125 and the last GPS point at t = 145. If the most distant GPS point identified is closer than ε (a predefined value established by the tracking server administrator 100 and stored on the tracking server 100) for the line segment between the first and the last point, so any points not currently marked to be saved can be discarded without the simplified curve having an inaccuracy worse than ε. If the point furthest from the line segment is greater than ε from the line segment, then this GPS point is maintained.
    [0046] The route creation module 205 recursively calls the RDP algorithm with the first point and the worst (that is, most distant) point and then with the worst point and the last point. In one embodiment, the route creation module 205 may stop recursion when the route creation module 205 determines that a sequence of GPS points that have been found to be potentially inaccurate represents a group of GPS points resulting from the transport vehicle being stationary . The route creation module 205 can determine that a sequence of GPS points results from the transport vehicle being stationary because it considers probable distributions of GPS noise inherent in the GPS data received from the location tracking device 101. The path creation module 205 removes points whose distribution corresponds to these characteristics of a stationary vehicle more closely than a vehicle in motion. By applying the RDP algorithm to GPS points classified as potentially inaccurate, the 205 route creation module creates a similar curve with fewer points.
    [0047] FIGURE 4 illustrates a simplified GPS route according to an embodiment. Similar to FIGURE 3, the route path associated with the map is represented by a continuous line in FIGURE 4. The dashed line shown in FIGURE 4 represents the simplified GPS route path. In particular, part 401 of the simplified GPS path represents the simplification of the transport vehicle's GPS path between time t = 125 and time t = 145 in FIGURE 3. As shown in FIGURE 4, the creation module route 205 simplified the GPS vehicle travel path between time t = 125 and time t = 145 to be a relatively straight line 401 shown in FIGURE 4.
    [0048] Referring again to FIGURE 2, the route determination module 119 additionally includes a selection module 205. In one embodiment, the selection module 205 selects a part of the route path associated with the map that corresponds to the points of potentially inaccurate GPS or the simplified part of the GPS route that corresponds to the potentially inaccurate GPS points on the final route of the transport vehicle. For example, with respect to FIGURE 4, the selection module 205 selects whether to include part 401 of the simplified GPS route path or part 403 of the route path associated with the map to include in the transport vehicle's final route path. The final route is representative of the transport vehicle's route to complete the journey.
    [0049] Selection module 205 determines whether to select the simplified part of the GPS route path based on a set of rules that govern the use of the simplified part of the GPS route path in relation to the route path associated with the map. In one embodiment, the selection module 205 selects the simplified part of the GPS route path if all the rules described below are satisfied. Otherwise, the route path associated with the map is selected by the selection module 205.
    [0050] Alternatively, the selection module 205 selects the simplified part of the GPS path if a subset of the rules described below is satisfied. The rules that are included in the subset balance between false positive selection of the simplified part of the GPS route path for inclusion in the final route path and false negatives where the route path associated with the map is incorrectly selected instead of the simplified part of the route path. GPS route. If the subset of rules is not satisfied, selection module 205 selects the route path associated with the map.
    [0051] To select the subset of rules, selection module 205 applies different subsets of rules for evaluation in relation to a set of training trips (for example, 10,000 trips). That is, selection module 205 applies different combinations of subsets of rules described below in relation to the set of training trips. Each trip in the training trip set can represent an actual trip that took place. Applying each subset of rules to the set of training trips results in the selection of a simplified part of the GPS route path or the route path associated with the map for inclusion in a final route path for each trip included in the travel set of training.
    [0052] Selection module 205 determines one or more sub-sets of rules that resulted in the most accurate selection of a simplified part of the GPS route path or the route path associated with the map for inclusion in the final route path. In one embodiment, selection module 205 determines a percentage of inaccuracy for each subset of rules under evaluation and selects a limit number of subsets of rules (for example, the top 5 subsets in relation to performance) for further evaluation.
    [0053] Selection module 205 can apply the selected subsets of rules to a set of verification trips (for example, another 10,000 trips) to verify that the selected subset of rules is not an overfitting for the set of training trips. That is, the selection module 205 additionally evaluates the selected subsets of rules to guarantee good performance through different trips. The verification trip set is distinct from the training trip set.
    [0054] After applying the selected subsets of rules to the verification travel set, the selection module 205 determines the subset of rules that resulted in the most accurate selection of a simplified part of the GPS route path or an associated route path with map for inclusion in the final route path for each of the trips included in the set of verification trips. The subset of rules with the best accuracy is selected for implementation on the tracking server 100. An illustrative subset of rules that results in the selection of the simplified part of the GPS route path while having a very low false positive rate (for example, below 5%) includes the "neighbor" rule, the "minimum candidate" rule, the "precision" rule, the deviation-based rules, the similarity-based rules, the distance-based rules, the "direction" rule "and the" curve "rule as described below.
    [0055] In one embodiment, the set of rules includes a "neighbor" rule that is based on the neighbors of the simplified part of the GPS route path. In one embodiment, the neighbor rule causes the 205 selection module to select the simplified part of the GPS route path for inclusion in the transport vehicle's final route path if the segments of the GPS path path that are directly adjacent to the simplified part the GPS route path are accurate. Referring again to FIGURE 4, part 405 and part 407 of the GPS path are neighbors of the simplified part 401 of the GPS path since they are directly adjacent to the simplified part 401. To determine the neighbors, the selection module 205 identifies sequentially ordered GPS point sequences that were received before and after the GPS points that are potentially inaccurate candidates are received. For example, selection module 205 identifies the GPS points in part 405 and the GPS points in part 407 as the sequences of GPS points that were respectively received before and after the candidate GPS points were received.
    [0056] The selection module 205 determines the error of estimation of the median position of the GPS points included in the neighboring parts. If the median horizontal accuracy is less than a limit value (for example, 15 meters), the selection module 205 selects the simplified part of the GPS route path for inclusion in the transport vehicle's final route path. Selection module 205 operates on the assumption that if the GPS data corresponding to the neighboring parts of the GPS route path is accurate, it is likely that the GPS data for the simplified part of the simplified GPS path path will be more reliable than the route path associated with the map.
    [0057] The set of rules may also include a "minimum bid" rule requiring that GPS points that are candidates to be inaccurate prior to simplification include a limited amount of GPS points. For example, the rule may specify that GPS points must include more than two GPS points that are candidates for being inaccurate. Selection module 205 can count how many GPS points are included in the candidates to be inaccurate and compare the count against a limit. If selection module 205 determines that the count is greater than the limit, selection module 205 determines that the minimum candidate rule is satisfied. Otherwise, the minimum candidate rule is not satisfied.
    [0058] The set of rules may also include a "time stamp" rule requiring that the time marks associated with the GPS points do not indicate a time interval between measurements of the GPS points that are greater than an amount timeout (for example, 10 seconds). In one embodiment, each GPS point is associated with a time stamp that indicates when the GPS point was measured by the location tracking device 101. Selection module 205 can analyze sequential pairs of GPS points to determine the amount of time that has elapsed since the GPS points were measured based on the time marks associated with the GPS points. If selection module 205 determines that the amount of time that elapsed from when all sequential pairs of GPS points were measured is less than the amount of timeout, selection module 205 determines that the time is satisfied. If the selection module 205 determines that the amount of time that has elapsed between measurements of any pair of GPS points is greater than the limit, the time stamp rule is not satisfied.
    [0059] The set of rules may also include a "city speed" rule requiring that the transport vehicle was moving at a speed less than a limit speed (for example, 45 meters per second) at the time when the GPS points that are candidates for being inaccurate were measured by the location tracking device 101. If the transport vehicle was traveling at a speed greater than the limit speed, the data received from the location tracking device 101 is likely to be inaccurate resulting in an artificial increase in the calculated speed of the transport vehicle.
    [0060] Selection module 205 can determine the travel speed of the location tracking device 101 by calculating the distance between the locations associated with any pair of adjacent GPS points included in the GPS points that are candidates to be inaccurate. Selection module 205 also determines the elapsed time from when the GPS point pairs were measured based on the time marks associated with the GPS point pairs. Selection module 205 determines the speed of the transport vehicle by calculating the distance quotient between the locations associated with the pairs of GPS points and the time elapsed from when the pairs of GPS points were measured. If the speed of the transport vehicle is less than the limit speed for all GPS pairs and points, the selection module 205 determines that the speed rule is satisfied. However, if the speed of the transport vehicle is greater than the limit speed for any pair of GPS points, selection module 205 determines that the speed rule is not satisfied.
    [0061] The set of rules may also include a "precision" rule that requires GPS points that are candidates to be inaccurate to have a median position estimation error that is less than an accuracy limit. In one embodiment, the accuracy limit is 15 meters. To determine the median position estimation error, selection module 205 determines the position estimation error for each GPS point compared to its corresponding point on the route path associated with the map as previously described above. Selection module 205 calculates the median position estimate error based on the position estimate errors calculated for the GPS points. If the median position estimation error is less than the precision limit, selection module 205 determines that the precision rule is satisfied. However, if the median position estimation error is greater than the precision limit, selection module 205 determines that the precision rule is not satisfied.
    [0062] In another embodiment of the precision rule, selection module 205 compares the error of estimating the median position of the GPS points that are candidates to be inaccurate with an error of estimating the median position of the entire trip. In one example, the error of estimating the median position of the entire trip is weighted by a factor of two. If the selection module 205 determines that the median position estimate error of the GPS points that are candidates to be inaccurate is less than the weighted median position estimate error for the entire trip, the precision rule is satisfied. Otherwise, the selection module 205 determines that the precision rule is not satisfied.
    [0063] The set of rules can also include one or more "deviation" rules. In one embodiment, the diversion rules include a rule that requires the deviation from the route path associated with the map to be greater than a weighted deviation from the simplified part of the GPS route path. The weight can be set by an administrator of the tracking server 100 to any value such as 1.25.
    [0064] Each potentially inaccurate crude GPS candidate is associated with a corresponding point on the route path associated with the map and with a corresponding point on the simplified part of the GPS route path. Selection module 205 calculates the deviation of the route path associated with the map by first measuring the distance between each potentially inaccurate candidate and their point corresponds on the route path associated with the map. The selection module 205 then identifies the average distance and associates the deviation of the route path associated with the map with the identified value.
    [0065] Similarly, selection module 205 calculates the deviation of the simplified part of the GPS route path by first measuring the distance between each candidate to be inaccurate and its corresponding point on the simplified part of the GPS path path. Selection module 205 then identifies the average distance and associates the deviation of the simplified GPS path with the identified value. Selection module 205 multiplies the deviation of the simplified part of the GPS route by the weighting fact. Finally, selection module 205 determines whether the deviation of the route path associated with the map is greater than the weighted deviation of the simplified part of the GPS route path to determine whether the rule is satisfied.
    [0066] Detour rules can also include an average deviation rule that requires the average deviation of the simplified part of the GPS route to be less than or equal to a limit distance such as 10 meters. To determine whether the average deviation rule is satisfied, selection module 205 measures the distance between each candidate to be inaccurate with its corresponding point on the simplified part of the GPS route path as mentioned above. The selection module 205 then calculates the average of the measured distances and compares the average with the limit distance. If the average is less than or equal to the limit distance, selection module 205 determines that the average deviation rule is satisfied.
    [0067] The deviation rules may also include a percentile rule that requires that the limit percentile (for example, 95%) of the deviations from the simplified part of the GPS route path be less than or equal to a limit distance such as 30 meters. To determine whether the percentile rule is satisfied, selection module 205 measures the distance between each candidate to be inaccurate with its corresponding point on the simplified part of the GPS route path as mentioned above. The selection module 204 then determines whether the limit percentile (for example, 95%) of the measured distances is less than or equal to the limit distance. If the limit percentile (for example, 95%) of the average distances is less than or equal to the limit distance, selection module 205 determines that the percentile rule is satisfied.
    [0068] The set of rules may also include one or more "similarity" rules. In one embodiment, the similarity rules include an average similarity rule that requires that the average similarity between the simplified GPS route path and its associated part on the map path associated with the map be greater than a limit distance (for example, 15 meters).
    [0069] As mentioned earlier, each of the points on the simplified GPS route path and the route path associated with the map are associated with time marks. Selection module 205 determines the similarity between the simplified GPS route path and its associated part in the map path associated route by determining time marks from the simplified GPS path path that are in a relative correspondence with time marks a from the route path associated with the map. Time marks are considered to be corresponding if they are within a second, for example. For each pair of corresponding time marks, selection module 205 determines the distance between the simplified GPS route path and the route path associated with the map. Selection module 205 then averages the distances. If the average of the distances is greater than the limit distance (for example, 15 meters), the selection module 205 determines that the rule of average similarity is met. Otherwise, the rule of average similarity is not satisfied.
    [0070] In one embodiment, the similarity rules include a "maximum" similarity rule. The maximum similarity rule requires that the maximum distance (that is, the longest) between the simplified GPS route path and the route path associated with a map with corresponding time marks be greater than a limit (for example, 25 meters) . To determine whether the maximum similarity rule is satisfied, selection module 205 determines the longest distance between the simplified GPS route path and the route path associated with a map with corresponding time marks. Selection module 205 compares the longest distance to the limit (for example, 25 meters). If the longest distance is greater than the limit, selection module 205 determines that the maximum similarity rule is satisfied.
    [0071] The set of rules also includes a "distance traveled" rule. The distance traveled rule specifies that the difference in distance traveled between the simplified GPS route path and the corresponding part of the route path associated with the map is greater than a threshold percentage (for example, 25%). To determine whether the distance traveled rule is satisfied, the selection module 205 calculates the distance traveled both on the simplified GPS route and on the corresponding part of the route path associated with the map. If the selection module 205 determines that the distance traveled on the simplified GPS route path is greater than the limit percentage of the route path associated with the map, the distance traveled rule is satisfied.
    [0072] The set of rules can also include a "direction" rule. The direction rule specifies that the difference in the direction of travel between the simplified GPS route path and the corresponding part of the route path associated with the map is greater than a limit angle (for example, 10 degrees). To determine whether the steering rule is satisfied, selection module 205 calculates the route direction for the simplified GPS route path. To calculate the direction of travel for the simplified GPS travel path, selection module 205 determines the angle formed between the horizon and a line connecting the first point and the center of all points on the simplified GPS travel path. Similarly, to calculate the route direction for the corresponding part of the route path associated with the map, selection module 205 determines the angle formed between the horizon and a line connecting the first point and the center of all points on the route path. associated with map. In one embodiment, the difference in angles must be greater than a threshold angle (for example, 10 degrees) for selection module 205 to determine that the direction change rule is satisfied.
    [0073] Finally, the set of rules also includes a "curve" rule. The turn rule disapproves of a simplified GPS route that involves frequent turns. To determine whether the curve rule is satisfied, selection module 205 determines for each curve in the simplified GPS route the distance between the curve and the next subsequent curve, if any. Selection module 205 calculates an average distance traveled between curves and compares the average distance with a limit (for example, 15 meters). In a rendering, the selection module 205 determines that the curve rule is satisfied if the average distance traveled between curves is greater than the limit (for example, 15 meters).
    [0074] As described above, selection module 205 determines whether to include the simplified GPS route path in the transport vehicle's final route path based on whether a subset of rules described above is satisfied. In one embodiment, all the rules described in this document must be met so that the 205 selection module includes the simplified GPS route path in the transport vehicle's final route path. Alternatively, any combination of the rules described above must be satisfied as determined by a tracking server administrator 100 for selection module 205 to include the simplified GPS route path in the transport vehicle's final route path.
    [0075] Selection module 205 includes the selected part of the route path associated with the map or the simplified GPS route path in the final route path of the transport vehicle. In one embodiment, the selection module 205 connects the simplified part of the GPS route path with the route path associated with a neighboring map to establish the final route path of the transport vehicle. If the selection module 205 selects the part of the route path associated with the map for inclusion in the final route path of the transport vehicle, the selection module 205 uses the route path associated with the map as the final route path of the transport vehicle. transport. For example, FIGURE 5 shows the final route of a journey completed by the transport vehicle. The final route of the trip includes the simplified part 401 of the GPS route shown in FIGURE 4.
    [0076] Returning to FIGURE 1, tracking server 100 also includes a fare calculation module 121. Fare calculation module 121 calculates fares for completed trips. In one embodiment, the fare calculation module 121 calculates a fare for a completed trip based on the completed route route for a trip that includes simplified parts of the GPS route path described above. By basing the fare on the completed route route rather than on the GPS route path, tracking server 100 calculates the most accurate fare possible.
    [0077] To calculate the fare, the fare calculation module 121 cal calculates the distance from the initial location of a trip to the destination location of the trip along the completed route path. For example, the fare calculation module 121 determines the distance in miles or meters from the initial location of the trip to the destination location of the trip. The fare calculation module 121 then determines the cost per distance traveled (for example, cost per mile such as $ 1.30 per mile) for the trip. The cost per distance traveled is associated with the geographical location associated with the trip. For example, the cost per distance traveled for the Sem Francisco Bay area, California, may be different than the cost per distance traveled for Los Angeles, California. The fare calculation module 121 multiplies the cost per distance traveled by the distance traveled to determine the distance component of the fare.
    [0078] In one embodiment, the fare for a trip is also based on the amount of time required to complete the trip. The fare calculation module 121 can determine the amount of time it takes to complete the trip based on the time marks associated with the GPS points received from the location tracking device 101 and multiplies the time at a cost per elapsed time (for example, cost per minute) to calculate the time component of the fare. The cost per time traveled may also be dependent on the geographic location associated with the trip.
    [0079] In one embodiment, the fare for a trip is also associated with a basic fare. The basic fare is a basic minimum that the person who requested the trip will be charged for the trip. The fare calculation module 121 can add the distance component, the time component and the basic fare to determine the fare for the trip. The fare calculation module 121 then applies a payment method to the person who requested the trip (for example, debits a credit card) and communicates the fare to the service application 109 of the person's service requesting device 102. Through the techniques described in this document, the enhancement for tariff calculation is a technical improvement that allows for a more accurate calculation of distance that is now available through conventional GPS measurement technology.
    [0080] Referring again to FIGURE 1, a historical GPS database 115 stores final travel routes completed by the transport vehicles. Thus, the historical GPS database 115 stores a travel history (for example, route paths) completely by different transport vehicles. In one embodiment, the historic GPS database 115 stores GPS coordinates of the transport vehicles used to complete trips specified in GPS 115 database. GPS coordinates can be stored in the form of a list or table.
    [0081] A map construction module 123 updates the map database 114 based on the travel history stored in the historical GPS database 115. The map construction module 123 uses the travel history to update road information stored in the map database 113. For example, the travel history included in the historical GPS database 115 may include trips that have been completed via road segments that do not exist according to the map database 113. The map building module 123 can update the map database 113 to include road segments used to complete trips stored in the historic GPS database 115. For example, FIGURE 5 illustrates the map of the area in which a trip has been completed. As shown in FIGURE 5, the trip was completed via a road segment 501 that is not in the map database 113. FIGURE 6 illustrates an updated map of the area where the trip was completed. As shown in FIGURE 6, the map building module 123 added a road segment 601 to the map.
    [0082] In one embodiment, the map construction module 123 adds a track segment to the map database 113 if the track segment is used for at least a limit number of trips, for example, 50 trips. If the map building module 123 determines that the road segment is used for at least the limit number of trips, the map building module 123 adds the road segment to the map database 113 as long as sufficient trips have been completed. via the track segment to precisely determine that a track actually exists. If the map construction module 123 determines that the track segment is not used in the limit number of trips, the map construction module 123 refrains from adding the track segment to the map database 113. Thus, the Map construction module 123 ensures that the road segment is actually existing before updating the map database 113.
    [0083] FIGURE 7A illustrates an embodiment of a flowchart of the method for determining a trip by a transport vehicle. Note that in other embodiments, steps other than those shown in FIGURE 7 can be performed to determine the trip for the transport vehicle.
    [0084] In one embodiment, the tracking server 100 receives 701 GPS data describing a trip from a transport vehicle. GPS data is received from a location tracking device 101 located inside the transport vehicle. According to some examples, GPS data can be received during the progress of the journey and associated with the journey (for example, until the journey is completed). Subsequently, in one example, the tracking server 100 can perform one or more steps of FIGURE 7A after the journey is completed. As an addition or alternative, the tracking server 100 can perform one or more steps of FIGURE 7A, such as steps 703 through 707, while the journey is in progress.
    [0085] Tracking server 100 identifies 703 candidate GPS data from received GPS data that is potentially inaccurate. The candidate may be inaccurate due to noise in the GPS signal. Tracking server 100 determines that a given GPS is a candidate to be inaccurate by comparing GPS points included in the GPS data with points included in a route path associated with a map for the trip.
    [0086] Tracking server 100 simplifies 705 a portion of the trip that is associated with candidate GPS data that is inaccurate. By simplifying the part of the trip that is potentially inaccurate, tracking server 100 minimizes the inaccuracy of the route path taken by a transport vehicle to complete the trip as reported by location tracking device 101. Tracking server 100 selects 707 the trip associated with a map of the simplified part of the trip for inclusion in the final representation of the trip. The tracking server 100 can make the selection based on the rules previously described above.
    [0087] The tracking server 100 finalizes 709 to the final data of the trip based on the selection. Finalizing the trip data comprises the tracking server 100 including the selected part of the trip on the final route path for the trip. Tracking server 100 can then perform one or more operations, for example, post-trip processing, using trip data, such as (i) generating a map with an image of the final route overlaid on the map for a receipt in the application or receipt via email to the requester and / or the service provider, (ii) calculate 711 a fare for the trip based on the final route of the trip, (iii) cause the respective payment or financial mechanism of the requester and / or the service provider is charged and / or credited, and / or (iv) transmits data for the receipt to the respective devices.
    [0088] FIGURE 7B illustrates an embodiment of a flowchart of the method for updating a vehicle map based on a travel of a transport vehicle according to one embodiment. Note that in other embodiments, steps other than those shown in FIGURE 7B can be performed.
    [0089] In one embodiment, the tracking server 100 receives 713 GPS data describing a trip from a transport vehicle. The tracking server 100 identifies 715 candidate GPS data from the received GPS data that is potentially inaccurate. Tracking server 100 simplifies 717 a portion of the trip that is associated with candidate GPS data that is inaccurate. By simplifying the part of the trip that is potentially inaccurate, tracking server 100 minimizes the inaccuracy of the route taken by a transport vehicle until it completes the trip as reported by the location tracking device 101. Tracking server 100 selects 719 the trip associated with the map or the simplified part of the trip for inclusion in the final representation of the trip. The tracking server 100 can make the selection based on the rules previously described above.
    [0090] The tracking server 100 finalizes 721 the final trip based on the selection. Finalizing the journey comprises the tracking server 100 including the selected portion of the journey on the final route path for the journey. Tracking server 100 updates 723 a vehicle map based on the final trip as well as including routes used on the final trip that are not on the vehicle map. Hardware Components
    [0091] FIGURE 8 is a diagram illustrating a computer system in which embodiments described in this document can be implemented. For example, in the context of FIGURE 1, the tracking server 100 can be implemented using a computer system as described by FIGURE 8. The tracking server 100 can also be implemented using a combination of various computer systems as described by FIGURE 8.
    [0092] In an implementation, the tracking server 100 includes processing resources 801, main memory 803, read-only memory (ROM) 805, storage device 807, and a communication interface 809. The communication server tracking 100 includes at least one processor 801 for processing information and a main memory 803, such as a random access memory (RAM) or other dynamic storage device, for storing information and instructions to be executed by the processor 801. The memory principal 803 can also be used to store temporary variables or other intermediate information while executing instructions to be executed by processor 801. Tracking server 100 can also include ROM 805 or another static storage device to store static information and instructions for processor 801. The 807 storage device, such as a magnetic disk or optical disk, is provided to store information and instructions.
    [0093] The communication interface 809 may allow the tracking server 100 to communicate with one or more networks (for example, cellular network) through the use of the network link (using wires or without using wires). Using the network link, the tracking server 100 can communicate with one or more computing devices, and with one or more servers. In some variations, tracking server 100 can be configured to receive sensor data (for example, such as GPS data) from one or more location tracking devices via the network link. The sensor data can be processed by the 801 processor and can be stored, for example, in the 807 storage device. The 801 processor can process the sensor data from a location tracking device in order to determine the travel path. of a transport vehicle corresponding to the location tracking device. The extrapolated position information can be transmitted to one or more service requesting devices over the network 105 to allow service applications 109 running on the service requesting devices to use the position information to present a visualization of the actual movement of the transport vehicles. .
    [0094] The tracking server 100 can also include a video device 811, such as a cathode ray tube (CRT), an LCD monitor, or a television set, for example, to display graphics and information to a user. An input mechanism 813, such as a keyboard that includes alphanumeric keys or other keys, can be coupled with tracking server 100 to communicate information and command selections to processor 801. Other non-limiting illustrative examples of input mechanisms 813 include a mouse, a TrackBall, a touchscreen, or cursor direction keys to communicate direction information and command selections to the 801 processor and to control the movement of the cursor on the 811 display device.
    [0095] Examples described in this document are related to the use of the tracking server 100 to implement the techniques described in this document. According to one embodiment, these techniques are performed by the tracking server 100 in response to processor 801 by executing one or more sequences of one or more instructions contained in main memory 803. Such instructions can be read into main memory 803 from another machine-readable medium, such as the storage device 807. The execution of the instruction sequences contained in main memory 803 causes the processor 801 to perform the process steps described in this document. In alternative implementations, printed circuit systems can be used instead or in combination with the software instructions to implement examples described in this document. Thus, the examples described are not limited to any specific combination of hardware and software circuit systems.
    [0096] FIGURE 9 is a diagram illustrating a mobile computing device in which embodiments described in this document can be implemented. In one embodiment, a computing device 900 can correspond to a mobile computing device, such as a cellular device that is capable of telephony, messaging, and data services. The computing device 900 can correspond to each of the location tracking device 101 and the service requesting device 103. Examples of such devices include smartphones, transmitting / receiving devices or tablet for cellular operators. Computing device 900 includes a processor 905, memory resources 909, a video device 901 (for example, such as a touchscreen device), one or more communication subsystems 911 (including wireless communication subsystems) , 903 input mechanisms (for example, an input mechanism may include or be part of the touch sensitive video device), and one or more location detection mechanisms (for example, GPS module) 907. In one example , at least one of the 911 communication subsystems sends and receives cellular data via data channels and voice channels.
    [0097] The 905 processor is configured with software and / or other logic to perform one or more processes, steps and other functions described with the implementations, such as those described in this document. The 905 processor is configured with instructions and data stored in the 909 memory resources to operate a service application as described in this document. For example, instructions for operating the service application to display user interfaces can be stored in memory resources 909 of computing device 900.
    [0098] From a service provider's point of view, a service provider operating a location tracking device 101 can operate service application 111 so that sensor data, such as location / position data, can can be determined from the location detection mechanism 907. This location / position data can then be transmitted wirelessly to the system via the 911 communication subsystems. From an end user's point of view, a user can operate service application 109 in order to receive position information from one or more transport vehicles from the system (via communication subsystems 911).
    [0099] The 905 processor can provide content for the 901 video by executing instructions and / or applications that are stored in the 909 memory resources. In some examples, one or more user interfaces may be provided by the 905 processor, such as a user interface for the service application, based at least in part on the position information received from one or more transport vehicles. Although FIGURE 9 is illustrated for a mobile computing device, one or more embodiments can be implemented on other types of devices, including fully functional computers, such as laptops and desktop computers (for example, PC).
    [00100] Reference in the specification to "the embodiment" or "an embodiment means that a particular aspect, structure or feature is included in at least one embodiment of the disclosure. The appearances of the phrase" in an embodiment "or" a preferred embodiment "in the various places in the specification are not necessarily referring to the same implementation.
    [00101] Some parts of the above are presented in terms of methods and symbolic representations of operations in relation to bits of data within a computer memory. These descriptions and representations are the means used by those skilled in the art to more effectively convey the substance of their work to others skilled in the art. A method is here, and generally, designed to be a self-consistent sequence of steps (instructions) leading to a desired result. The steps are these requiring physical manipulations of physical quantities. Usually, although not necessarily, these quantities take the form of electrical, magnetic or optical signals capable of being stored, transferred, combined, compared and otherwise manipulated. Sometimes it is convenient, mainly for reasons of common use, to refer to these signs as bits, values, elements, symbols, characters, terms, number, among others. In addition, sometimes it is also convenient to refer to some stage arrangements requiring physical manipulation of physical quantities such as modules or code devices, without loss of generality.
    [00102] However, it should be borne in mind that all of these terms and similar terms are to be associated with appropriate physical quantities and are simply convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions using terms such as "processing" or "computation" or "calculating" or "displaying" or "determining", among others, refer to the action and processes of a computer system, or similar electronic computing device, which manipulates and transforms data represented as physical (electronic) quantities within the memories or registers of the computer system or other information storage , broadcast, or video devices.
    [00103] Some aspects described in this document include process steps and instructions described in this document in the form of a method. It should be noted that the process steps and instructions described in this document can be incorporated into software, firmware or hardware, and when incorporated into software, they can be transferred to reside and be operated from different platforms used by various operating systems.
    [00104] The embodiments discussed above also relate to an apparatus for performing the operations in this document. This apparatus may be specially built for the required purposes, or it may comprise a general purpose computer selectively activated or reconfigured by a computer program stored on the computer. Such a computer program can be stored on a non-transitory computer-readable storage medium, such as, but not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic / optical disks, read-only memories ( ROMs), random access memory (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application-specific integrated circuits (ASICs), or any type of medium suitable for storing electronic instructions, and each coupled with a system bus. computer. In addition, the computers referred to in the specification can include a single processor or can be architectures employing multiple processor designs for increased computing capacity.
    [00105] The methods and exposures presented in this document are inherently related to any particular computer or other device. Various general purpose systems can also be used with programs according to the instructions in this document, or it may prove convenient to build a more specialized device to perform the required method steps. The structure required for several of these systems will appear from the description below. In addition, the embodiments are not described with reference to any particular programming language. It will be appreciated that several programming languages can be used to implement the instructions described in this document, and any references below to the specific languages are provided for enabling disclosure and best mode.
    [00106] Although the disclosure has been particularly presented and described with reference to a preferred embodiment and several alternative embodiments, it will be understood by those skilled in the relevant technique that various changes in form and details can be made in them without departing from the spirit and the scope of the invention.
    [00107] Finally, it should be noted that the language used in the specification was mainly selected for reading ability and instructional purpose, and may not have been selected to outline or circumscribe the subject of the invention. Accordingly, the disclosure is intended to be illustrative, but not limiting, of the scope of the invention.
    权利要求:
    Claims (11)
    [0001]
    1. Computer-implemented method to calculate a fare for a trip, the method characterized by the fact that it comprises: receiving global positioning satellite (GPS) data for a vehicle describing a trip by vehicle from an initial location to a location destination along a route; predict a vehicle's route from the initial location to a destination location based on known highway segments in a map database (113) and the vehicle's GPS data; identify a plurality of candidate GPS points from the GPS data that is potentially inaccurate due to noise in the GPS data, the candidate GPS points located along a part of the route and the plurality of candidate GPS points corresponding to positions geographic areas that are not associated with known road segments in the map database; simplify the part of the route; determine whether to include in the route the part of the simplified route or a part of the planned route that corresponds to the plurality of candidate GPS points based on a set of rules; select the part of the simplified route or the part of the route planned to include in the route based on the determination; review the route based on the selection; calculate a fare for the trip from the initial location to the destination location based on the revised route; and transmitting fare information for the trip to a computing device (900) associated with a user account.
    [0002]
    2. Method implemented by computer, according to claim 1, characterized by the fact that the GPS data are received from a location tracking device (101) located in the transport vehicle.
    [0003]
    3. Method implemented by computer, according to claim 1, characterized by the fact that identifying the plurality of candidate GPS points comprises: comparing GPS points from the GPS data with the predicted route path; determine the accuracy of each GPS point based on the comparison of each GPS point with the predicted route path; and determining the plurality of candidate GPS points based on the accuracy of each of the plurality of GPS points.
    [0004]
    4. Method implemented by computer, according to claim 1, characterized by the fact that simplifying the part of the route comprises: applying a Ramer-Douglas-Peucker algorithm in the plurality of candidate GPS points to generate the simplified part.
    [0005]
    5. Method implemented by computer, according to claim 1, characterized by the fact that the set of rules includes a rule requiring that the plurality of candidate GPS points include a limit amount of GPS points, the method still comprising: counting a number of GPS points included in the plurality of candidate GPS points; compare the count with a limit; and select the simplified part for inclusion in the revised route based on the count exceeding the limit.
    [0006]
    6. Method implemented by computer, according to claim 1, characterized by the fact that the set of rules includes a rule requiring that the time elapsed between the measurement of each of the plurality of candidate GPS points be less than a limit, the method further comprising: determining a length of time elapsed from when the location tracking device (101) measured each sequential pair of candidate GPS points included in the plurality of candidate GPS points; compare the duration of time with the limit; and select the simplified part for inclusion in the revised route based on each length of time being less than the limit.
    [0007]
    7. Method implemented by computer, according to claim 1, characterized by the fact that the set of rules includes a rule requiring that the speed of the transport vehicle when the plurality of candidate GPS points were measured is less than a limit speed, the method further comprising: calculating a transport vehicle speed between each sequential pair of candidate GPS points when the plurality of candidate GPS points were measured; compare the calculated speed with the speed limit; and select the simplified part for inclusion in the revised route in response to the calculated speed being less than the speed limit.
    [0008]
    8. Method implemented by computer, according to claim 1, characterized by the fact that the set of rules includes a rule requiring that the accuracy of the plurality of candidate GPS points is less than an accuracy limit, the method still comprising : calculate a median precision of the plurality of candidate GPS points in relation to the vehicle's expected route path; and select the simplified part for inclusion in the revised route in response to the median precision being less than the precision limit.
    [0009]
    9. Method implemented by computer, according to claim 1, characterized by the fact that calculating the fare comprises: determining a distance traveled by the vehicle based on the revised route; and calculate the fare for the trip based, at least in part, on the given distance.
    [0010]
    10. Method implemented by computer, according to claim 1, characterized by the fact that the method still comprises: updating the map database (113) to include one more road segments corresponding to the geographical positions of the plurality of points of GPS candidates based on the route being revised to include the simplified part.
    [0011]
    11. Method, according to claim 1, characterized by the fact that the set of rules includes a neighbor rule specifying to select the simplified route path for inclusion in the final route path based on an accuracy of GPS points that are neighbors to the plurality of points associated with the simplified part, the determination comprising: identifying, from the vehicle's GPS data, a first plurality of sequentially ordered GPS points that were received before the plurality of candidate GPS points associated with the simplified part being received; identify, from the vehicle's GPS data, a second plurality of sequentially ordered GPS points that were received after the plurality of candidate GPS points associated with the simplified part that was received; identifying a first precision associated with the first plurality of sequentially ordered GPS points and a second precision associated with the second plurality of sequentially ordered GPS points; and select the simplified part for inclusion in the revised route based on the first precision and the second precision.
    类似技术:
    公开号 | 公开日 | 专利标题
    BR112018015201B1|2021-02-23|METHOD IMPLEMENTED BY COMPUTER TO CALCULATE A FEE FOR A TRIP
    US20170309083A1|2017-10-26|Determining an Amount for a Toll Based on Location Data Points Provided by a Computing Device
    US8954266B2|2015-02-10|Providing routes through information collection and retrieval
    US9500486B2|2016-11-22|Method and apparatus for formulating a positioning extent for map matching
    US10215575B2|2019-02-26|Identifying a map matched trip from received geographic position information
    US10415984B2|2019-09-17|Measuring the accuracy of map matched trajectories
    TW201111744A|2011-04-01|Method of verifying or deriving attribute information of a digital transportation network database using interpolation and probe traces
    US20080294337A1|2008-11-27|Travel-related information processing system
    US10533862B1|2020-01-14|Biasing map matched trajectories based on planned route information
    US10119824B2|2018-11-06|Method and apparatus for updating road map geometry based on probe data
    Velaga et al.2012|Improving the performance of a topological map-matching algorithm through error detection and correction
    US20200080865A1|2020-03-12|Providing Navigable Environment Plots
    US10915914B2|2021-02-09|Method, apparatus, and computer program product for incentivizing travel along road segments
    Noulas et al.2018|Developing and deploying a taxi price comparison mobile app in the wild: Insights and challenges
    US10900795B2|2021-01-26|Method and system for identifying meeting points
    CN112868036A|2021-05-28|System and method for location recommendation
    BR112019022761A2|2020-08-18|dynamic support information based on contextual information
    US20210123748A1|2021-04-29|Detecting defects in map data
    US20170146355A1|2017-05-25|Method and apparatus for selectively qualifying trajectories in regards to a determination of travel time for a maneuver
    JP6678476B2|2020-04-08|Travel route estimation device and travel route estimation method
    US20190390972A1|2019-12-26|Polyline matching to map data for routing a trip
    US10515549B1|2019-12-24|Method, apparatus, and computer program product for evaluating public transportation use
    US20200402394A1|2020-12-24|Adjusting historical probe data for new road geometry
    JP6706308B2|2020-06-03|Information processing system and information processing method
    JP2019028526A|2019-02-21|Congestion prediction device
    同族专利:
    公开号 | 公开日
    CA3011825A1|2017-08-03|
    EP3408614A1|2018-12-05|
    US9939276B2|2018-04-10|
    US20170219360A1|2017-08-03|
    AU2016390056B2|2019-05-02|
    AU2016390056A1|2018-08-02|
    CA3011825C|2020-06-30|
    EP3408614A4|2020-02-12|
    US20180238691A1|2018-08-23|
    US10620009B2|2020-04-14|
    BR112018015201A2|2018-12-26|
    WO2017130047A1|2017-08-03|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US5917434A|1995-06-15|1999-06-29|Trimble Navigation Limited|Integrated taximeter/GPS position tracking system|
    US5917424A|1996-12-31|1999-06-29|At & T Corp|Duplicate page sensor system and method|
    AU2467401A|1999-10-21|2001-04-30|Sabre Inc.|Method and apparatus for searching for a low fare for travel between two locations|
    KR101073166B1|2005-03-07|2011-10-12|주식회사 현대오토넷|Taximeter and method for calculating cap-fare using navigation system|
    US8099237B2|2008-07-25|2012-01-17|Navteq North America, Llc|Open area maps|
    US8195393B2|2009-06-30|2012-06-05|Apple Inc.|Analyzing and consolidating track file data|
    WO2011023247A1|2009-08-25|2011-03-03|Tele Atlas B.V.|Generating raster image representing road existence probability based on probe measurements|
    US20140067490A1|2012-08-30|2014-03-06|Frias Transportation Infrastructure Llc|For-hire vehicle fare and parameter calculation system and method|
    US9671233B2|2012-11-08|2017-06-06|Uber Technologies, Inc.|Dynamically providing position information of a transit object to a computing device|
    US9939276B2|2016-01-28|2018-04-10|Uber Technologies, Inc.|Simplifying GPS data for map building and distance calculation|US9939276B2|2016-01-28|2018-04-10|Uber Technologies, Inc.|Simplifying GPS data for map building and distance calculation|
    DE102016214156A1|2016-08-01|2018-02-01|Continental Teves Ag & Co. Ohg|A method of sending data from a vehicle to a server and method of updating a map|
    EP3322149A1|2016-11-10|2018-05-16|Tata Consultancy Services Limited|Customized map generation with real time messages and locations from concurrent users|
    US10679312B2|2017-04-25|2020-06-09|Lyft Inc.|Dynamic autonomous vehicle servicing and management|
    US10916076B2|2017-04-25|2021-02-09|Ford Global Technologies, Llc|Method and apparatus for adaptive vehicle route-related data gathering|
    US10732635B2|2017-12-30|2020-08-04|Lyft Inc.|Localization based on sensor data|
    US11015941B2|2018-05-25|2021-05-25|Here Global B.V.|Method and apparatus for path based map matching|
    US10657821B2|2018-06-13|2020-05-19|Whelen Engineering Company, Inc.|Autonomous intersection warning system for connected vehicles|
    US20200013243A1|2018-07-03|2020-01-09|Honeywell International Inc.|Systems and methods for enhanced cyber security by data corruption detection monitoring|
    US11081010B2|2018-10-18|2021-08-03|Transfinder Corporation|Automatically pairing GPS data to planned travel routes of mobile objects|
    US11168989B2|2019-01-02|2021-11-09|Here Global B.V.|Supervised point map matcher|
    JP2020118507A|2019-01-22|2020-08-06|本田技研工業株式会社|Guide device, guide method, and program|
    US10531224B1|2019-03-11|2020-01-07|Whelen Engineering Company, Inc.|System and method for managing emergency vehicle alert geofence|
    CN110515110B|2019-09-05|2021-08-10|北京百度网讯科技有限公司|Method, device, equipment and computer readable storage medium for data evaluation|
    CN111121791A|2019-11-29|2020-05-08|上饶市中科院云计算中心大数据研究院|Optimization method of hidden Markov model in map matching and GPS positioning method|
    法律状态:
    2020-06-09| B06A| Notification to applicant to reply to the report for non-patentability or inadequacy of the application [chapter 6.1 patent gazette]|
    2020-12-15| B09A| Decision: intention to grant [chapter 9.1 patent gazette]|
    2021-02-23| B16A| Patent or certificate of addition of invention granted|Free format text: PRAZO DE VALIDADE: 20 (VINTE) ANOS CONTADOS A PARTIR DE 31/12/2016, OBSERVADAS AS CONDICOES LEGAIS. |
    2021-08-03| B25G| Requested change of headquarter approved|Owner name: UBER TECHNOLOGIES, INC. (US) |
    优先权:
    申请号 | 申请日 | 专利标题
    US15/009,552|2016-01-28|
    US15/009,552|US9939276B2|2016-01-28|2016-01-28|Simplifying GPS data for map building and distance calculation|
    PCT/IB2016/058127|WO2017130047A1|2016-01-28|2016-12-31|Simplifying gps data for map building and distance calculation|
    [返回顶部]